package greed

func partitionLabels(s string) (partition []int) {
	lastPos := [26]int{}
	for i, c := range s {
		lastPos[c - 'a'] = i
	}
	// lastPos 保存的是每个字符在s中出现的最后位置的下标
	start, end := 0, 0
	for i, c := range s {
		if lastPos[c -'a'] > end {
			end = lastPos[c - 'a']
		}
		if i == end {
			partition = append(partition, end -start + 1)
			start = end + 1
		}
	}
	return 
}